package com.berchen.offer;

/**
 *请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
 *
 * 二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
 *
 * 二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
 */
public class Test12 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        TreeNode node6=new TreeNode(2);
        TreeNode node10=new TreeNode(3);
        TreeNode node5=new TreeNode(4);
        TreeNode node7=new TreeNode(5);
        TreeNode node9=new TreeNode(6);
        TreeNode node11=new TreeNode(7);
//        node6.left=node5;
//        node6.right=node7;
        node10.left=node9;
        node10.right=node11;
        root.left=node6;
        root.right=node10;

        Test12 test12 = new Test12();
        String serialize = test12.Serialize(root);
        System.out.println(serialize);
    }
    String Serialize(TreeNode root) {

        if(root==null){
            return "";
        }
        StringBuilder inn=new StringBuilder();
        StringBuilder pre=new StringBuilder();
        preOrder(root,pre);
        innOrder(root,inn);

        return pre.substring(0,pre.lastIndexOf("-"))+"="+inn.substring(0,inn.lastIndexOf("-"));
    }
    TreeNode Deserialize(String str) {

        if("".equals(str)){
            return null;
        }
        String[] split = str.split("=");
        String pre=split[0];
        String inn=split[1];

        String[] preArr = pre.split("-");
        String[] innArr = inn.split("-");

        int[] preintArr=new int[preArr.length];
        int[] innintArr=new int[innArr.length];
        for(int i =0;i<preArr.length;i++){
            preintArr[i]=Integer.parseInt(preArr[i]);
        }
        for(int i =0;i< innArr.length;i++){
            innintArr[i]=Integer.parseInt(innArr[i]);
        }
        return reConstructBinaryTree(preintArr,innintArr);

    }

    /**
     * 通过前序遍历和中序遍历 生成二叉树
     * @param pre
     * @param vin
     * @return
     */
    public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {

        if(pre.length==0||vin.length==0||pre.length!=vin.length){
            return null;
        }
        return diGui(pre,0,pre.length-1,vin,0,vin.length-1);
    }

    /**
     *
     * @param pre 前序遍历数组
     * @param ps    本次 需要用到的前序遍历数组 的数据的开始索引
     * @param pe    本次 需要用到的前序遍历数组 的数据的结束索引
     * @param vin   中序遍历数组
     * @param vs    本次 需要用到的中序遍历数组 的数据的开始索引
     * @param ve    本次 需要用到的中序遍历数组 的数据的结束索引
     * @return
     */
    public TreeNode diGui(int[] pre, int ps, int pe, int [] vin, int vs, int ve){
        if(ps>pe||vs>ve){
            return null;
        }
        if(ps==pe){
            return new TreeNode(pre[ps]);
        }
        // 该节点就是 可用的数据中的头节点
        int headVal=pre[ps];
        // 保存头节点在中序遍历序列中的索引
        int headIndex=0;
        for (int i = vs; i <=ve ; i++) {
            if(vin[i]==headVal){
                headIndex=i;
                break;
            }
        }
        // 左子树的个数（头节点索引-中序遍历的可用元素的第一个元素）
        int length=headIndex-vs;
        // 创建头节点
        TreeNode head=new TreeNode(headVal);

        // 左子树
        head.left=diGui(pre,ps+1,ps+length,vin,vs,headIndex-1);

        // 右子树
        head.right = diGui(pre, ps+length + 1, pe, vin, headIndex + 1, ve);
        return head;
    }

    /**
     * 中序遍历
     * @param node
     * @param inn
     */
    void innOrder(TreeNode node,StringBuilder  inn){

        if(node.left!=null){
            innOrder(node.left,inn);
        }
        inn.append(node.val+"-");
        if(node.right!=null){
            innOrder(node.right,inn);
        }
    }

    /**
     * 前序遍历
     * @param node
     * @param pre
     */
    void preOrder(TreeNode node,StringBuilder pre){
        pre.append(node.val+"-");
        if(node.left!=null){
            preOrder(node.left,pre);
        }
        if(node.right!=null){
            preOrder(node.right,pre);
        }
    }


}
